package NewCoder;

import java.util.ArrayList;

public class BM60 {
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        ArrayList<String> list=new ArrayList<>();
        dfs(list,new StringBuilder(),n,n);
        return list;
    }
    private void dfs(ArrayList<String> list,StringBuilder sb,int left,int right){
        if(left<0 || right<0) return;
        if(left>right){
            return;
        }
        if(left==0 && right==0){
            list.add(sb.toString());
            return;
        }
        sb.append("(");
        dfs(list,sb,left-1,right);
        sb.deleteCharAt(sb.length()-1);

        sb.append(")");
        dfs(list,sb,left,right-1);
        sb.deleteCharAt(sb.length()-1);

    }
}
